#include <bits/stdc++.h>
using namespace std;
class Solution
{
  public:
    bool IsPa(string &s, int i, int j, vector<vector<int>> &mem)
    {
        if (i >= j)
            return true;
        if (mem[i][j] != -1)
            return mem[i][j];
        if (s[i] != s[j])
            return mem[i][j] = false;
        return mem[i][j] = IsPa(s, i + 1, j - 1 ,mem);
    }
    int getLongestPalindrome(string A)
    {
        int n = A.size();
        // vector<vector<int>> mem(n + 1, vector<int>(n + 1, -1));
        int maxLength = 1;
        // for (int i = 0; i < A.size(); i++)
        // {
        //     for (int j = i; j < A.size(); j++)
        //     
        //         if (IsPa(A, i, j, mem))
        //         {
        //             maxLength = max(maxLength, j - i + 1);
        //         }
        //     }
        // }
        vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));
        for (int i = 0; i < n; i ++)
        {
            dp[i][i] = true;
        }
        for (int i = 0; i < n- 1; i++)
        {
            if (A[i] == A[i + 1])
            {
                dp[i][i + 1] = true;
                maxLength = 2;
            }
        }
        for (int l = 3; l <= n; l++)
        {
            for (int i = 0; i <= n - l; i++)
            {
                int j = i + l - 1;
                if (A[i] == A[j] && dp[i + 1][j - 1])
                {
                    dp[i][j] = true;
                    maxLength = max(maxLength, j - i + 1);
                }
            }
        }
            return maxLength;
    }
};